package leetcode;

public class RegularExpMatching10 {

	private static final int FRONT = -1;
	
	public static void main(String[] args) {
		System.out.println(isMatch("aa","a"));
		System.out.println(isMatch("aa","aa"));
		System.out.println(isMatch("aaa","aa"));
		System.out.println(isMatch("aa", "a*"));
		System.out.println(isMatch("aa", ".*"));
		System.out.println(isMatch("ab", ".*"));
		System.out.println(isMatch("aab", "c*a*b"));
		System.out.println(isMatch("ab", ".*c"));
		System.out.println(isMatch("aa", "a*"));
		System.out.println(isMatch("aaa", "aaaa"));
	}

	public static boolean isMatch(String s, String p) {
		return myMatch(s,s.length() - 1, p, p.length() - 1);
	}
	
	private static boolean myMatch(String s, int i, String p, int j) {
		if(j == FRONT)
			if(i == FRONT)
				return true;
			else
				return false;
		
		if(p.charAt(j) == '*') {
			if(i > FRONT && (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i)))
				if(myMatch(s, i - 1, p, j))
					return true;
			return myMatch(s, i, p, j - 2);
		}
		if(p.charAt(j) == '.' || (i > FRONT && p.charAt(j) == s.charAt(i)))
			return myMatch(s, i - 1, p, j - 1);
		return false;
	}

}
